package codeRandomThoughts.Test337打家劫舍III;

import codeRandomThoughts.utils.TreeNode;

public class Solution {
    public int rob(TreeNode root) {
        return traversal(root)[0];
    }

    /**
     * @param root 入口
     * @return res[0]: 当前节点的最高金额 res[1]: 当前节点的左右子树的最高金额
     */
    public int[] traversal(TreeNode root) {
        //遍历到叶子结点
        if (root.left == null && root.right == null) {
            //偷当前节点的金额
            return new int[]{root.val, 0};
        }

        //遍历左子树
        int[] left = new int[2];
        if (root.left != null) {
            left = traversal(root.left);
        }

        //遍历右子树
        int[] right = new int[2];
        if (root.right != null) {
            right = traversal(root.right);
        }

        //设定根节点的值
        int[] res = new int[2];
        res[0] = Math.max(left[0] + right[0], left[1] + right[1] + root.val);
        res[1] = left[0] + right[0];
        return res;
    }
}
